//https://www.bilibili.com/video/BV1d54y1f7B3?spm_id_from=333.788.videopod.episodes&vd_source=d6fe65f095f01f05591e89d810720ccc&p=20
// 2024-10-21

import java.util.LinkedList;
import java.util.Queue;

public class P027_省份数量_广度优先 {

    public static void main(String[] args) {
        System.out.println(fun(new int[][] {{1,1,0},{1,1,0},{0,0,1}}));
//        System.out.println(fun(new int[][] {5,5,5,20}));
    }

    private static int fun(int[][] citysConnexted) {
        int citys = citysConnexted.length;
        boolean[] visited = new boolean[citys];
        int provinces = 0;//计数器

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < citys; i++) {
            if (!visited[i]) {//未被访问
                // 广度优先 时间复杂度
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int k = queue.poll();
                    visited[k] = true;

                    // 找直接相连的城市
                    for (int j = 0; j < citys; j++)
                        if (citysConnexted[i][j] == 1 && !visited[j]) //未打标时候才需要判断
                            queue.offer(j);//入队
                }//找到一个省份
                provinces++;    //省份++
            }
        }
        return provinces;
    }
}
